Division
結果會有商/餘數
商 -> Lo
餘數 -> Hi
MIPS的除法裡面 它不會去做一些額外的檢查
1.發生了overflow
2.或是divided by zero
小時候所學過的長除法
嘗試著去把除數拿去減掉被除數
當被除數拿來減的部分是大於除數的
在這樣的情況下我們就會知道我們的商會大於 0
然後接下來我們就把商放上去
把值減完了之後剩下來的這個部分的餘數
會再跟被除數裡面比較低的位元重新結合在一起
然後繼續的去跟除數做比較
如果我們發現沒有辦法減下去
也就是說當我們完成這個減法的時候
發現減法得到的結果是負的值
那這時候我們必須要把它的值還原回去
然後把它的商填上0
依此類推直到最後一個位元
結論
如果可以減 那麼一樣我們的商會是大於零的
如果不能減 那麼我們的商就會等於0
在除法裡面被除數 除數通通最多都是32個bits
原理!!!
被除數不動
除數從一開始的最高位元
一路的一直移動到可以減到被除數的最低位元為止
第一版本
元件介紹
有64個bits的Divisor除數(實際上只有32bit放東西，其他是用來shift的)
被除數會跟Remainder放在一起
也是64個bits
ALU要拿來做減法也會有64個bits
因為我們可以知道我們實際上執行的是32個bits除以32個bits
也因此
我們的商最多也就只會只有32個bits
- 除數一開始是放在64bits的高位元的地方
- 至於被除數我們會永遠的停留在Remainder
第一次減:
這個減出來的結果一定會是負的值
因為在Remainder的高位元的地方它其實是零
至於Divisor這個部分
我們知道它絕對是一個大於零的整數
因此實際上執行完減法之後它的值一定會是負的
所以我們實際上必須要在商填一個零
接下來就要開始移動我們的除數讓它往低位元的方向移動
減完看看它的結果是正的還是負的
藉此來決定我們的商應該要是填甚麼樣的值
假如減出來的結果我們發現最後的餘數是負的
那麼意思就是
我們並不能夠真的把它減下去
所以我們的商必須要填零
而我們的餘數必須還原回在減法執行之前
也就是要還原為之前的餘數
...
最後一次的減法
當我們把除數移到最低位元的時候
演算法
我們是執行33次
之前的乘法運算 32個bits的乘法我們只要執行三十二次就好
理由
因為一開始的時候
除數是放在64個位元裡面的最高位元32bits的地方
然後我們必須要不斷地讓它往低位元的移動
我們都知道第一次的減法
其實減完的結果 商一定會是0
這次的減法好像沒有太大的意義
由此可知 在接下來第二個版本的除法運算裡面
我們當然會針對這個地方進行一系列的調整
這些調整 也會引發出新的問題
第二版本
改進
1.
其實在divisor的部分 我們一直只有用到32個bit
所以實際上當我們要進行減法的時候
我們的ALU應該也只要32個bit就好
2.
我們remainder的比較高位元的32個bit
其實從頭到尾我們也都沒用到
作法
因為我們的divisor 也就是我們的除數是向右移動的
如果我們現在希望它只要32個bit就好
那麼也就是說 我們希望它固定不動
如果當我們的divisor 也就是除數 固定不動
那麼我們的被除數很可能就必須要做相反的方向移動
就是我們把被除數的部分 讓它向左移動
商
其實一樣是要往左邊移動的
又因為我們原本我們的餘數 高位元的部分 就並沒有被使用到
乾脆把我們的被除數從低位元一路的往高位元移動
另一方面 我們直接把我們的商讓它填進我們的remainder的低位元的地方
這也就是為甚麼 我們的商 會放在64個bit暫存器裡面
LO的32個bit裡面
以及我們的餘數最後會放在HI的32個bit暫存器裡面
因為我們採用第二個版本的除法器設計
問題
我們一開始在前面做了一次減法
但是無論如何怎麼減 最後都必須要還原回來的
解決
原本 我們是先做減法 再做shift
我們現在改成是先做shift再做減法
但是 這個將來會造成一些問題
divisor除數只有32個bit ALU一樣也只剩下32個bit
我們是先做shift 然後再做減法
實際上我們減法會執行32次 但是我們的shift會是33次
因為一開始的時候我們先做了shift
演算法
如果我們shift了33個bit
那麼代表的意思是我們的餘數實際上它並沒有在HI的最低位元的地方開始
而是在HI的次低位元的地方開始
因此我們最後 必須要再把我們的餘數往右邊移動一個bit
如此一來 它才能夠跟HI這個暫存器的最低位元對齊
例子
前面我們一直提到 這個版本的調整有可能會造成一些問題
那麼請問 這會造成什麼樣的問題呢
在這裡 老師需要賣個關子
可是 我提供各位同學一些線索
1110/1111
會發生奇怪現象
Signed Division
我們一開始可以先把它們的符號拿出來
然後把它們都改成正的數字
分別的去做除法 除完之後我們會得到商以及餘數
商跟餘數在處理的時候 要掌握一個原則
就是被除數通常跟餘數應該是相同的sign 也就是相同的符號
無論如何 除法的運算一定要滿足
[被除數會等於商乘上除數再加上餘數]
只要能夠滿足這樣子的式子 基本上這就是一個除法的運算
看完了乘法與除法的運算之後 想想看我們是不是有可能把這兩個運算 通通用相同的硬體來實作呢
對乘法來說我們乘完的結果總共會有64個bit
而對於除法來說 我們的商還有餘數也是64個bit
在乘法運算裡面 我們會不斷的讓我們的乘積 我們的product向右移動
而在除法運算裡面 我們會把我們的餘數remainder
以及我們的商quotient向左移動
指令整理
